#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("inline")

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <ctime>
#include <cmath>
#include <set>
#include <cstdlib>
#include <algorithm>
using namespace std;

// 数据结构定义区
struct Server{
    int id;  // 服务器编号
    string type;  // 服务器型号
    int cpu;  // 总的cpu
    int mem;  // 总的内存
    int cpu_A, cpu_B;  // A B 节点cpu剩余量
    int mem_A, mem_B;  // A B 节点内存剩余量
    int hardware_cost;  // 硬件花费
    int day_cost;  // 每日能耗花费
    int f = 0;  // 双节点虚拟机数目
    unordered_set<int> vms_id;  // 存放部署在该服务器上的虚拟机id
};

struct VM{
    int id;  // 虚拟机ID
    string type;  // 虚拟机型号
    int cpu;
    int mem;
    bool isTwoNodes;  // 是否双节点部署
    int serverID;  // 该虚拟机所部署服务器的ID
    int assign_node;  // 该虚拟机安装在服务器的A节点则为1，B节点则为2
    string s; // 记录每个虚拟机的答案
};

struct Query{
    string type;  // 请求类型：add 或 del
    string vm_type;  // 创建时虚拟机类型
    int vm_id;  // 虚拟机ID
};

class ServerManager{
public:
    vector<Server> servers;  // 存放所有的服务器
    vector<Server> ID2Server;  // 建立ID到服务器的索引
    unordered_map<string, Server> type2Server;  // 建立类型到服务器的索引
    unordered_map<string, int> num;  // 存放当前每种类型的服务器数目
    int serverID = -1;  // 建立服务器ID，每次新增服务器则此ID加1
    static bool isEmpty(Server &server);  // 查看当前服务器是否为空
    long long getEnergyCost();  // 计算当前开机的服务器一天的能耗
    long long getHardwareCost();  // 计算当前买服务器的花费
};

class VmManager{
public:
    int num = 0;  // 当前存活的虚拟机数目
    unordered_map<string, VM> type2VM;  // 建立类型到虚拟机的索引
//    unordered_map<int, VM> ID2VM;  // 建立ID到虚拟机的索引
    vector<VM> ID2VM;
    int getMigrationNum() const;  // 获取可以的迁移次数
};

// 方法申明区
bool server_cmp(const Server &s1, const Server &s2);
bool server_cmp2(int a, int b);
bool vm_cmp(int a, int b);
bool vm_balance_cmp(int a, int b);
bool query_cmp(const Query &q1, const Query &q2);
int getIndex(int cpu, int mem);     // 根据cpu/mem分类
int getFitness(Server &server, VM &vm, int node);
inline void countRes(int day);     //
// 购买
string chooseBestServer(VM &vm);
string chooseBestServer2(vector<Query> &dayQuery, int flag);
// 部署
bool tryAssign(VM &vm);
// 重部署
void exchangeVms(VM &vm1, VM &vm2);     // 交换两个虚拟机的部署
void deployTransfer();     // 部署时的转移算法
vector<int> getAllFittedVm(Server &server, unordered_set<int> &set);
void reAssign(int last);
// 迁移
bool tryAssignForMigration(VM &vm, vector<int> &temp);
bool tryAssignForMigration(VM &vm, set<pair<int, int>> &s);
void migrationProcess(int &sz, vector<int> &temp, set<pair<int, int>> &s, vector <string> &res);
void exchangeEmptyServer(int &sz, vector<string> &res);
vector<string> migration();
void migrationBalance(int &sz, vector <string> &res);
// 操作
bool canAssign(Server &server, VM &vm, int node);
void doAssign(Server &server, VM &vm, int node);
void undoAssign(Server &server, VM &vm, int node);
void delVm(VM &vm);
// 输入输出
vector<Query> reorderQuery(vector<Query> &dayQuery);
vector<Query> readDayQuery();
void readData();
void processOutput(int last, vector<string> &mig, vector <Query> &dayQuery);

// 全局变量区
ServerManager serverManager;
VmManager vmManager;
vector<vector<Query>> query;   // 处理每天的请求
unordered_set<int> addVmGroup;   // 最近连续add的虚拟机id集合
unordered_set<int> delVmToday;  // 当天要删除虚拟机id
int leftDays, migrationNum = 0;
int addNums = 0; // 请求创建虚拟机指令数目
int cpu_res = 0; //每天的服务器cpu 剩余数量
int mem_res = 0; //每天的服务器mem 剩余数量
int cpu_a = 0;
int mem_b = 0;

unordered_map<int, int> trueid2id;
unordered_map<int, int> id2trueid;
int VMID_CNT = 0;   // 虚拟机id编号


//#define DEBUG
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#ifdef DEBUG
    clock_t begin = clock();
    freopen("../training-1.txt", "r", stdin);
//    freopen("../training-2_res.txt", "w", stdout);
    long long hardware_cost = 0, day_cost = 0;
#endif
    // 读取服务器和虚拟机数据
    readData();
    // 读取前K天请求
    int T, K; cin >> T >> K;
    for(int i = 0; i < K; i ++ ){
        query.push_back(readDayQuery());
    }
    // 处理每天的请求并输出结果
    leftDays = T;
    for(int i = 0; i < T; i ++ ) {
#ifdef DEBUG
        printf("have processed day=%d\n", i+1);  // 打印天数
        day_cost += serverManager.getEnergyCost();  // 计算昨天日花费
#endif
        leftDays -- ;
        addVmGroup.clear();  // 清空最近连续add虚拟机集合
        delVmToday.clear();  // 今天要迁移的虚拟机id集合
        for(auto &q: query[i]) {
            if(q.type == "del") delVmToday.insert(q.vm_id);
        }
        // 处理迁移
        vector<string> mig;
        countRes(i);
        mig = migration();
        // 重新排序今天的请求
        auto &dayQuery = query[i];
        vector<Query> dayQuery_ordered = reorderQuery(dayQuery);
        // 处理今日请求
        int last = serverManager.serverID;
        string serverType = chooseBestServer2(dayQuery_ordered, 2);
        string serverType1 = chooseBestServer2(dayQuery_ordered, 1);
        string serverType2 = chooseBestServer2(dayQuery_ordered, 0);
        for(auto &q: dayQuery_ordered){
            VM &vm = vmManager.ID2VM[q.vm_id];
            if(q.type == "add"){
                addVmGroup.insert(q.vm_id);   // 虚拟机id加入到最近连续add请求集合中
                vmManager.num ++ ;
                addNums ++ ;
                // 从现在已有的服务器中看能否部署此虚拟机，如果能则挑一个最适合的服务器来部署
                bool f = tryAssign(vm);
                // 如果不能部署，则新买一个服务器部署
                if(!f){
                    // 从若干种服务器类型中选出一种来部署
                    serverManager.serverID ++ ;
                    if(vm.cpu > vm.mem * 5) serverType = serverType1;
                    if(vm.cpu < vm.mem / 5) serverType = serverType2;

                    // 要购买的服务器
                    Server server = serverManager.type2Server[serverType];
                    server.id = serverManager.serverID;
                    if(vm.isTwoNodes) doAssign(server, vm, 0);
                    else doAssign(server, vm, 1);  // 单节点部署默认放在A节点
                    if(vm.isTwoNodes) server.f ++ ;
                    serverManager.ID2Server.push_back(server);
                    serverManager.num[serverType] ++ ;
                }
            }else if(q.type == "del"){
                // 500w
                reAssign(last);
                deployTransfer();     // 对最近的连续add进行重新部署
                addVmGroup.clear();     // 清空最近连续add请求的虚拟机集合
                vmManager.num -- ;
                delVm(vm);  // 删除此虚拟机
            }
        }
#ifndef DEBUG
        processOutput(last, mig, dayQuery);
#endif
        // 每次处理完一天后，如果有下一天，则读取下一天数据
        if(query.size() < T){
            query.push_back(readDayQuery());
        }
    }
#ifdef DEBUG
    hardware_cost += serverManager.getHardwareCost();
    day_cost += serverManager.getEnergyCost();
    clock_t end = clock();
    cout << "hardware_cost: " << hardware_cost << ", energy_cost: " << day_cost << endl;
    cout << "total cost: " << hardware_cost + day_cost << endl;
    cout << "migration num: " << migrationNum << endl;
    cout << "cost time: " << (end - begin)/CLOCKS_PER_SEC << "s" << endl;
#endif
    return 0;
}

bool server_cmp(const Server &s1, const Server &s2){  // 性价比比较
    int t = leftDays;
    return s1.hardware_cost + t * s1.day_cost  <
           s2.hardware_cost + t * s2.day_cost;
}

bool server_cmp2(int a, int b){  // 按照cpu和mem空闲率从大到小排序，这些可以先把空闲率比较高的服务器清空
    auto &t1 = serverManager.ID2Server[a], &t2 = serverManager.ID2Server[b];
    double s1 = 1.0 * (t1.cpu_A + t1.cpu_B) / t1.cpu + 1.0 * (t1.mem_A + t1.mem_B) / t1.mem;
    double s2 = 1.0 * (t2.cpu_A + t2.cpu_B) / t2.cpu + 1.0 * (t2.mem_A + t2.mem_B) / t2.mem;
    if(max(s1 - s2, s2 - s1) < 0.02) return t1.day_cost > t2.day_cost;
    return s1 > s2;
}

bool vm_cmp(const int a, const int b){  // 先部署单节点；先部署cpu+mem大的
    VM &vm1 = vmManager.ID2VM[a], &vm2 = vmManager.ID2VM[b];
    if(vm1.isTwoNodes != vm2.isTwoNodes) return vm1.isTwoNodes < vm2.isTwoNodes;
    return vm1.cpu + vm1.mem > vm2.cpu + vm2.mem;
}

bool vm_balance_cmp(int a, int b){   // 移走vm后，server的cpu/mem比例 - servertype 的cpu/mem 比列 越小越好；
    VM &vm1 = vmManager.ID2VM[a], &vm2 = vmManager.ID2VM[b];
    Server &server =serverManager.ID2Server[vm1.serverID];
    int ser_cpu=server.cpu_A+server.cpu_B;
    int ser_mem=server.mem_A+server.mem_B;
    int vm1_cpu=vm1.cpu + int(vm1.isTwoNodes) * vm1.cpu;
    int vm1_mem=vm1.mem + int(vm1.isTwoNodes) * vm1.mem;
    int vm2_cpu=vm2.cpu + int(vm2.isTwoNodes) * vm2.cpu;
    int vm2_mem=vm2.mem + int(vm2.isTwoNodes) * vm2.mem;
    double rate =server.cpu/server.mem;
    double d1=abs(1.0*(ser_cpu + vm1_cpu)/(ser_mem + vm1_mem)-rate);
    double d2=abs(1.0*(ser_cpu + vm2_cpu)/(ser_mem + vm2_mem)-rate);
    return d1<d2;
}

bool query_cmp(const Query &q1, const Query &q2){
    VM &v1 = vmManager.ID2VM[q1.vm_id], &v2 = vmManager.ID2VM[q2.vm_id];
    if(v1.isTwoNodes != v2.isTwoNodes) return v1.isTwoNodes > v2.isTwoNodes;
    int t1 = v1.cpu + v1.mem;
    int t2 = v2.cpu + v2.mem;
    return t1 > t2;
}

string chooseBestServer2(vector<Query> &dayQuery, int flag) {
    int cpu = 0, mem = 0;
    for(auto &q: dayQuery){
        if(q.type == "del") continue;
        VM &vm = vmManager.type2VM[q.vm_type];
        if(flag == 1 && vm.cpu < vm.mem / 5) continue;
        if(flag == 0 && vm.cpu > vm.mem * 5) continue;
        cpu += vm.cpu, mem += vm.mem;
        if(vm.isTwoNodes)
            cpu += vm.cpu, mem += vm.mem;
    }
    if(mem == 0) mem = 1.0;
    double f1 = 1.0 * cpu / mem;
    map<double, Server> sortedServer;  // 按照差距从小到大排序
    for(auto &server: serverManager.servers){
        double f2 = 1.0 * server.cpu / server.mem;
        double d = f1 - f2;
        if(d < 0) d = -d;
        sortedServer[d] = server;
    }
    Server ret;
    vector<Server> temp;  // 挑选四个最接近的服务器
    for(auto &it: sortedServer){
        Server &server = it.second;
        bool can = true;  // 判断该服务器能否装下所有虚拟机
        for(auto &q: dayQuery){
            VM &vm = vmManager.type2VM[q.vm_type];
            if(server.cpu_A < vm.cpu || server.mem_A < vm.mem){
                can = false;
                break;
            }
        }
        if(can){
            temp.push_back(server);
        }
        if(temp.size() >= 10) break;
    }
    // 选择性价比最高的一款
    sort(temp.begin(), temp.end(), server_cmp);
    ret = temp[0];
    return ret.type;
}

vector<string> migration() {
    vector<string> res;  // 存放每次转移的信息
    int sz = vmManager.getMigrationNum();  // 可迁移次数
    vector<int> temp;  // 从小到大存放拥有虚拟机数目的服务器ID
    vector<int> candidate;  // 存放本次迁移可以放置的服务器
    set<pair<int, int>> s;  // 存放{cpu+mem, 服务器id}的有序集合，默认会以cpu+mem从小到大排序

    migrationBalance(sz,res);

    for(int i = 0; i <= serverManager.serverID; i ++ ) {
        Server &server = serverManager.ID2Server[i];
        // 空闲率
        double t = 1.0 * (server.cpu_A + server.cpu_B + server.mem_A + server.mem_B) / (server.cpu + server.mem);
        if(t < 0.02 && server.vms_id.size() > 1) continue;  // TODO t < 0.0075
        if(ServerManager::isEmpty(server)) continue;
        temp.push_back(i);
//        s.insert({server.cpu_A + server.cpu_B + server.mem_A + server.mem_B, server.id});
    }
    long long before = serverManager.getEnergyCost();
    for(int i = 0; i < 5; i ++ ){
        migrationProcess(sz, temp, s, res);
        long long after = serverManager.getEnergyCost();
        if(before - after <= 0) break;
    }
    exchangeEmptyServer(sz, res);
    return res;
}

void migrationBalance(int &sz, vector <string> &res) { // 平衡极端情况
    // 服务器类型如果几乎集中在某一种类型则   不需要  平衡
    int nums=0;
    vector<double> type_rate;
    for(auto it=serverManager.num.begin();it!=serverManager.num.end(); ++it) {nums+=it->second;}
    for(auto it=serverManager.num.begin();it!=serverManager.num.end(); ++it){
        type_rate.emplace_back((1.0*it->second/nums));
    }
    sort(type_rate.begin(),type_rate.end());

    if(type_rate.size()<=1) return;
    else if( (type_rate.back()-type_rate[type_rate.size()-2])>0.5) return;

    if(sz <= 0) return;
    vector<int> nobalance;
    set<pair<int, int>> s_balance;  // 存放{cpu+mem, 服务器id}的有序集合，默认会以cpu+mem从小到大排序
    for(int i = 0; i <= serverManager.serverID; i ++ ) {
        Server &server = serverManager.ID2Server[i];
        if(ServerManager::isEmpty(server)) continue;
        int res_cpu = server.cpu_A + server.cpu_B;
        int res_mem = server.mem_A + server.mem_B;
        if(res_cpu==0&&res_mem==0) continue;
        double res_rate = 1.0*(res_cpu+0.01)/(res_mem+0.01);
        // 当前服务器cpu/mem 与 原本  服务器cpu/mem  是否适配；
        if(res_rate>(0.2*server.cpu/server.mem) && res_rate< (5.0*server.cpu/server.mem)) {
            s_balance.insert({server.cpu_A + server.cpu_B + server.mem_A + server.mem_B, server.id});
        }else{
            nobalance.emplace_back(i);      //    cpu/mem   与本类型不匹配
        }
    }
    for(int i = 0; i < nobalance.size(); i++ ){
        int id = nobalance[i];
        auto &server = serverManager.ID2Server[id];
        vector<int> vmsId;
        for(auto &vmId: server.vms_id){
            vmsId.push_back(vmId);
        }
        sort(vmsId.begin(),vmsId.end(),vm_balance_cmp);
        for(int vmId: vmsId){
            VM &vm = vmManager.ID2VM[vmId];
            int a = vm.serverID, b = vm.assign_node;
            if(sz <= 0) return;
            int res_cpu = server.cpu_A + server.cpu_B;
            int res_mem = server.mem_A + server.mem_B;
            double res_rate = 1.0*(res_cpu+0.01)/(res_mem+0.01);
            // 当前服务器cpu/mem 与 原本  服务器cpu/mem 适配； 则退出 平衡
            if(res_rate>(0.2*server.cpu/server.mem) && res_rate< (5.0*server.cpu/server.mem)) {
                break;
            }
            auto it = s_balance.find({server.cpu_A + server.cpu_B + server.mem_A + server.mem_B, server.id});
            if(it != s_balance.end()) s_balance.erase(it);
            undoAssign(server, vm, b);
            s_balance.insert({server.cpu_A + server.cpu_B + server.mem_A + server.mem_B, server.id});
            bool f = tryAssignForMigration(vm, s_balance);
            if(f){
                if(a == vm.serverID && b == vm.assign_node) continue;  // 未迁移
                migrationNum ++ ;
                string s = to_string(id2trueid[vm.id]) + ", " + to_string(vm.serverID);
                if(vm.assign_node == 1) s += ", A";
                if(vm.assign_node == 2) s += ", B";
                res.push_back("(" + s + ")");
                sz -- ;
            }else{
                auto it = s_balance.find({server.cpu_A + server.cpu_B + server.mem_A + server.mem_B, server.id});
                if(it != s_balance.end()) s_balance.erase(it);
                doAssign(server, vm, b);
                s_balance.insert({server.cpu_A + server.cpu_B + server.mem_A + server.mem_B, server.id});
            }
        }
    }
}

void migrationProcess(int &sz, vector<int> &temp, set<pair<int, int>> &s, vector <string> &res) {
    if(sz <= 0) return;
    sort(temp.begin(), temp.end(), server_cmp2);
    for(int i = 0; i < temp.size(); i ++ ){
        int id = temp[i];
        auto &server = serverManager.ID2Server[id];
        vector<int> vmsId;
        for(auto &vmId: server.vms_id){
            if(delVmToday.count(vmId) > 0) {
                if(rand()%5 == 1)
                    continue; // 今日要被删除的，则20%概率不做迁移
            }
            vmsId.push_back(vmId);
        }
        sort(vmsId.begin(), vmsId.end(), vm_cmp);
        if(vmsId.size() <= 2) temp[i] = 0;
        for(int vmId: vmsId){
            VM &vm = vmManager.ID2VM[vmId];
            int a = vm.serverID, b = vm.assign_node;
            if(sz <= 0) return;
//            auto it = s.find({server.cpu_A + server.cpu_B + server.mem_A + server.mem_B, server.id});
//            if(it != s.end()) s.erase(it);
            undoAssign(server, vm, b);
//            s.insert({server.cpu_A + server.cpu_B + server.mem_A + server.mem_B, server.id});
            bool f = tryAssignForMigration(vm, temp);
            if(f){
                if(a == vm.serverID && b == vm.assign_node) continue;  // 未迁移
                migrationNum ++ ;
                string s = to_string(id2trueid[vm.id]) + ", " + to_string(vm.serverID);
                if(vm.assign_node == 1) s += ", A";
                if(vm.assign_node == 2) s += ", B";
                res.push_back("(" + s + ")");
                sz -- ;
            }else{
//                auto it = s.find({server.cpu_A + server.cpu_B + server.mem_A + server.mem_B, server.id});
//                if(it != s.end()) s.erase(it);
                doAssign(server, vm, b);
//                s.insert({server.cpu_A + server.cpu_B + server.mem_A + server.mem_B, server.id});
            }
        }
        temp[i] = id;
    }
}

void exchangeEmptyServer(int &sz, vector<string> &res) {
    while(sz > 0){
        vector<int> emptyServer, fullServer;
        for(int id = 0; id <= serverManager.serverID; id ++ ){
            if(ServerManager::isEmpty(serverManager.ID2Server[id])){
                emptyServer.push_back(id);
            }else{
                fullServer.push_back(id);
            }
        }
        int save = 0, s = -1, t = -1; // 将s中虚拟机部署到t上能省多少电费
        for(auto from: fullServer){
            for(auto id: emptyServer ){
                Server &s1 = serverManager.ID2Server[from];
                Server &s2 = serverManager.ID2Server[id];
                int d = s1.day_cost - s2.day_cost;
                if(d <= save) continue;
                save = d;
                if(s1.cpu / 2 - s1.cpu_A <= s2.cpu_A && s1.cpu / 2 - s1.cpu_B <= s2.cpu_B &&
                   s1.mem / 2 - s1.mem_A <= s2.mem_A && s1.mem / 2 - s1.mem_B <= s2.mem_B){
                    s = from, t = id, save = d;
                }
            }
        }
        if(s == -1) break;
        Server &s1 = serverManager.ID2Server[s];
        Server &s2 = serverManager.ID2Server[t];
        if(sz < s1.vms_id.size()) break;
        // 将s1上虚拟机部署到s2上面
        for(auto &vmId: s1.vms_id){
            VM &vm = vmManager.ID2VM[vmId];
            doAssign(s2, vm, vm.assign_node);
            migrationNum ++ ;
            string str = to_string(id2trueid[vm.id]) + ", " + to_string(vm.serverID);
            if(vm.assign_node == 1) str += ", A";
            if(vm.assign_node == 2) str += ", B";
            res.push_back("(" + str + ")");
            sz -- ;
        }
        s1.vms_id.clear();
        s1.cpu_A = s1.cpu_B = s1.cpu / 2;
        s1.mem_A = s1.mem_B = s1.mem / 2;
    }
}

bool tryAssignForMigration(VM &vm, set<pair<int, int>> &s) {
    int resFitness = INT32_MIN, resID = -1, resNode = -1;
    set<pair<int, int>>::iterator it, resIt;
    int target = vm.cpu + vm.mem;
    if(vm.isTwoNodes) target += target;
    it = s.lower_bound({target, -1});
    for(; it != s.end(); it ++ ){
        int id = it->second;
        Server &server = serverManager.ID2Server[id];
//        if(vm.serverID == server.id && server.vms_id.size() <= 2) continue;
        if(vm.isTwoNodes) {
            if (canAssign(server, vm, 0)) {  // 判断当前服务器cpu和内存能部署此虚拟机
                int fitness = getFitness(server, vm, 0);
                if(fitness > resFitness){
                    resFitness = fitness;
                    resID = id;
                    resNode = 0;
                    resIt = it;
                }
//                if(resID != -1 && fitness > -1e7) break;
            }
        }else{
            if(canAssign(server, vm, 1)){
                int fitness = getFitness(server, vm, 1);
                if(fitness > resFitness){
                    resFitness = fitness;
                    resID = id;
                    resNode = 1;
                    resIt = it;
                }
            }else if(canAssign(server, vm, 2)){
                int fitness = getFitness(server, vm, 2);
                if(fitness > resFitness){
                    resFitness = fitness;
                    resID = id;
                    resNode = 2;
                    resIt = it;
                }
            }
        }
    }
    // 如果没有一台服务器能部署此虚拟机则直接返回false
    if(resID == -1) return false;
    // 部署此虚拟机
    Server &server = serverManager.ID2Server[resID];
    s.erase(resIt);
    doAssign(server, vm, resNode);
    s.insert({server.cpu_A + server.cpu_B + server.mem_A + server.mem_B, server.id});
    return true;
}

bool tryAssign(VM &vm) {
    int resFitness = INT32_MIN, resID = -1, resNode = -1;
    for(int id = 0; id <= serverManager.serverID; id ++ ){
        Server &server = serverManager.ID2Server[id];
        if(vm.isTwoNodes) {
            if (canAssign(server, vm, 0)) {  // 判断当前服务器cpu和内存能部署此虚拟机
                int fitness = getFitness(server, vm, 0);
                if(fitness > resFitness){
                    resFitness = fitness;
                    resID = id;
                    resNode = 0;
                }
            }
        }else{
            if(canAssign(server, vm, 1)){
                int fitness = getFitness(server, vm, 1);
                if(fitness > resFitness){
                    resFitness = fitness;
                    resID = id;
                    resNode = 1;
                }
            }else if(canAssign(server, vm, 2)){
                int fitness = getFitness(server, vm, 2);
                if(fitness > resFitness){
                    resFitness = fitness;
                    resID = id;
                    resNode = 2;
                }
            }
        }
    }
    // 如果没有一台服务器能部署此虚拟机则直接返回false
    if(resID == -1) return false;
    // 部署此虚拟机
    Server &server = serverManager.ID2Server[resID];
    doAssign(server, vm, resNode);
    return true;
}

/* 将最近连续add请求中部署的虚拟机进行“迁移”，看能否部署到更好的服务器 */
void deployTransfer(){
    vector<int> vm_add_group(addVmGroup.begin(), addVmGroup.end());
    int size = vm_add_group.size();
    for(int id: vm_add_group){
        VM &vm = vmManager.ID2VM[id];
        if(vm.isTwoNodes) continue;
        Server &server = serverManager.ID2Server[vm.serverID];
        int node = vm.assign_node;
        undoAssign(server, vm, node);
        bool f = false;
        if(node == 1 && canAssign(server, vm, 2) && getFitness(server, vm, 2) > getFitness(server, vm, 1)){
            doAssign(server, vm, 2);
            f = true;
        }
        if(node == 2 && canAssign(server, vm, 1) && getFitness(server, vm, 1) > getFitness(server, vm, 2)){
            doAssign(server, vm, 1);
        }
        if(!f) doAssign(server, vm, node);
    }
    for(int i=0; i<size-1; ++i){
        for(int j=i+1; j<size; ++j){
            VM &vm1 = vmManager.ID2VM[vm_add_group[i]];
            VM &vm2 = vmManager.ID2VM[vm_add_group[j]];
            exchangeVms(vm1, vm2); // 尝试交换
        }
    }
}

void exchangeVms(VM &vm1, VM &vm2){
    int vm1_node = vm1.assign_node;
    int vm2_node = vm2.assign_node;
    // 如果两个虚拟机都部署在同一个服务器，或一个双节点，一个单节点部署，则不交换
    if(vm1.serverID==vm2.serverID || vm1_node==0 && vm2_node!=0 || vm1_node!=0 && vm2_node==0) return;

    Server &server1 = serverManager.ID2Server[vm1.serverID];
    Server &server2 = serverManager.ID2Server[vm2.serverID];

    // 先从原服务器undoAssign
    undoAssign(server1, vm1, vm1_node);
    undoAssign(server2, vm2, vm2_node);

    // 判断交换后是否满足可部署条件
    if(!canAssign(server2, vm1, vm2_node) || !canAssign(server1, vm2, vm1_node)){
        doAssign(server1, vm1, vm1_node);
        doAssign(server2, vm2, vm2_node);
        return;
    }

    // 交换后fitness更大则交换，否则部署回原来的情况
    bool exchange_flag; // = getFitness(server2, vm1, vm2_node) > getFitness(server1, vm1, vm1_node) || getFitness(server1, vm2, vm1_node) > getFitness(server2, vm2, vm2_node);
    if(addVmGroup.size() > 60){  // 当前连续add较多时，激进的交换策略 ||
        exchange_flag = getFitness(server2, vm1, vm2_node) > getFitness(server1, vm1, vm1_node) || getFitness(server1, vm2, vm1_node) > getFitness(server2, vm2, vm2_node);
    }else{      // 当前连续add较少时，保守的交换策略  &&
        exchange_flag = getFitness(server2, vm1, vm2_node) > getFitness(server1, vm1, vm1_node) && getFitness(server1, vm2, vm1_node) > getFitness(server2, vm2, vm2_node);
    }
    if(exchange_flag){
        doAssign(server2, vm1, vm2_node);
        doAssign(server1, vm2, vm1_node);
    }else{
        doAssign(server1, vm1, vm1_node);
        doAssign(server2, vm2, vm2_node);
    }
}

void reAssign(int last){  // 重新部署虚拟机
    vector<int> vm_add_group(addVmGroup.begin(), addVmGroup.end());
    unordered_set<int> s(addVmGroup.begin(), addVmGroup.end());
    unordered_map<int, pair<int, int>> old; // 记录虚拟机部署所在服务器id和节点
    for(int id: vm_add_group) {
        VM &vm = vmManager.ID2VM[id];
        Server &server = serverManager.ID2Server[vm.serverID];
        old[id] = {vm.serverID, vm.assign_node};
        undoAssign(server, vm, vm.assign_node);
    }

    for(int id = 0; id <= serverManager.serverID; id ++ ){
        if(s.empty()) break;
        Server &server = serverManager.ID2Server[id];
        while(true) {
            vector<int> candidate = getAllFittedVm(server, s);  // 获取服务器能装下的所有虚拟机id
            if (candidate.empty()) break;
            int bestId = -1, node = -1;
            int dif = INT32_MIN;
            for(int vmId: candidate){
                VM &vm = vmManager.ID2VM[vmId];
                if(vm.isTwoNodes){
                    int d = getFitness(server, vm, 0);
                    if(d > dif){
                        dif = d;
                        bestId = vmId;
                        node = 0;
                    }
                }else{
                    if(canAssign(server, vm, 1)){
                        int d = getFitness(server, vm, 1);
                        if(d > dif){
                            dif = d;
                            bestId = vmId;
                            node = 1;
                        }
                    }
                    else if(canAssign(server, vm, 2)){
                        int d = getFitness(server, vm, 2);
                        if(d > dif){
                            dif = d;
                            bestId = vmId;
                            node = 2;
                        }
                    }
                }
            }
            doAssign(server, vmManager.ID2VM[bestId], node);
            s.erase(bestId);
        }
    }
    if(!s.empty()){
        for(int id: vm_add_group){
            if(s.count(id)) continue;
            VM &vm = vmManager.ID2VM[id];
            Server &server = serverManager.ID2Server[vm.serverID];
            undoAssign(server, vm, vm.assign_node);
        }
        for(int id: vm_add_group){
            VM &vm = vmManager.ID2VM[id];
            int serverId = old[id].first, node = old[id].second;
            Server &server = serverManager.ID2Server[serverId];
            doAssign(server, vm, node);
        }
    }
}

vector<int> getAllFittedVm(Server &server, unordered_set<int> &s) {
    vector<int> ret;
    for(int id: s){
        VM &vm = vmManager.ID2VM[id];
        if(vm.isTwoNodes && canAssign(server, vm, 0)) ret.push_back(id);
        else if(!vm.isTwoNodes && (canAssign(server, vm, 1) ||
                                   canAssign(server, vm, 2))) ret.push_back(id);
    }
    return ret;
}

bool tryAssignForBalance(VM &vm, set<pair<int, int>> &s) {
    int resFitness = INT32_MIN, resID = -1, resNode = -1;
    set<pair<int, int>>::iterator it, resIt;
    int target = vm.cpu + vm.mem;
    if(vm.isTwoNodes) target += target;
    it = s.lower_bound({target, -1});
    for(; it != s.end(); it ++ ){
        int id = it->second;
        Server &server = serverManager.ID2Server[id];
        if(vm.isTwoNodes) {
            if (canAssign(server, vm, 0)) {  // 判断当前服务器cpu和内存能部署此虚拟机
                int fitness = getFitness(server, vm, 0);
                if(fitness > resFitness){
                    resFitness = fitness;
                    resID = id;
                    resNode = 0;
                    resIt = it;
                }
                if(resID != -1 && fitness > -1e7) break;
            }
        }else{
            if(canAssign(server, vm, 1)){
                int fitness = getFitness(server, vm, 1);
                if(fitness > resFitness){
                    resFitness = fitness;
                    resID = id;
                    resNode = 1;
                    resIt = it;
                }
            }else if(canAssign(server, vm, 2)){
                int fitness = getFitness(server, vm, 2);
                if(fitness > resFitness){
                    resFitness = fitness;
                    resID = id;
                    resNode = 2;
                    resIt = it;
                }
            }
        }
    }
    // 如果没有一台服务器能部署此虚拟机则直接返回false
    if(resID == -1) return false;
    // 部署此虚拟机
    Server &server = serverManager.ID2Server[resID];
    s.erase(resIt);
    doAssign(server, vm, resNode);
    s.insert({server.cpu_A + server.cpu_B + server.mem_A + server.mem_B, server.id});
    return true;
}

bool tryAssignForMigration(VM &vm, vector<int> &temp) {
    int resFitness = INT32_MIN, resID = -1, resNode = -1;
    for(int id: temp){
        Server &server = serverManager.ID2Server[id];
        if(vm.isTwoNodes) {
            if (canAssign(server, vm, 0)) {  // 判断当前服务器cpu和内存能部署此虚拟机
                int fitness = getFitness(server, vm, 0);
                if(fitness > resFitness){
                    resFitness = fitness;
                    resID = id;
                    resNode = 0;
                }
            }
        }else{
            if(canAssign(server, vm, 1)){
                int fitness = getFitness(server, vm, 1);
                if(fitness > resFitness){
                    resFitness = fitness;
                    resID = id;
                    resNode = 1;
                }
            }else if(canAssign(server, vm, 2)){
                int fitness = getFitness(server, vm, 2);
                if(fitness > resFitness){
                    resFitness = fitness;
                    resID = id;
                    resNode = 2;
                }
            }
        }
    }
    // 如果没有一台服务器能部署此虚拟机则直接返回false
    if(resID == -1) return false;
    // 部署此虚拟机
    Server &server = serverManager.ID2Server[resID];
    doAssign(server, vm, resNode);
    return true;
}

int getIndex(int cpu, int mem) {
    double ratio = 1.0 * cpu / mem;
    if (ratio < 0.75) return 0;
    else return 1;
}

inline void countRes(int day){
    cpu_res=0;
    mem_res=0;
    auto &dayQuery = query[day];

    for(int id = 0; id <= serverManager.serverID; id ++ ) {
        Server &server = serverManager.ID2Server[id];
        cpu_res+=(server.cpu_A+server.cpu_B);
        mem_res+=(server.mem_A+server.mem_B);
    }

    for(auto &q:dayQuery){
        VM &vm = vmManager.ID2VM[q.vm_id];
        if(q.type == "add"){
            cpu_res+=(vm.cpu + static_cast<int>(vm.isTwoNodes)*vm.cpu);
            mem_res+=(vm.mem + static_cast<int>(vm.isTwoNodes)*vm.mem);
        }

    }

    if(cpu_res>0&&mem_b>0){
        cpu_a= static_cast<int>((1.0*mem_res/(cpu_res+mem_res))*200);
        mem_b= static_cast<int>((1.0*cpu_res/(cpu_res+mem_res))*200);
    }else{
        cpu_a=100;
        mem_b=100;
    }

#ifdef DEBUG
    //cout<<" cpu_res  "<<cpu_res<<" mem_res  "<<mem_res<<endl;
    //cout<<" cpu_a    "<<cpu_a  <<" mem_a    "<<mem_b<<endl;
#endif
}

inline int getFitness(Server &server, VM &vm, int node) {
    int a = 100, b = 40;
    int d1 = a * (server.cpu_A - vm.cpu) + b * (server.mem_A - vm.mem);
    int d2 = a * (server.cpu_B - vm.cpu) + b * (server.mem_B - vm.mem);

    d1 = -d1, d2 = -d2;
    bool isEmpty = server.cpu_A + server.cpu_B == server.cpu && server.mem_A + server.mem_B == server.mem;
    if(node == 0) {
        int d = d1 + d2;
        if(isEmpty) d -= 1000000 * server.day_cost;
        return d;
    }
    else if(node == 1) {
        if(isEmpty) d1 -= 1000000 * server.day_cost;
        return d1;
    }
    else {
        if(isEmpty) d2 -= 1000000 * server.day_cost;
        return d2;
    }
}

string chooseBestServer(VM &vm) {
    vector<Server> temp;
    int d = 3;
    for(auto &server: serverManager.servers){
        if(getIndex(vm.cpu, vm.mem) != getIndex(server.cpu, server.mem)) continue;
        if(server.cpu_A <= vm.cpu + d || server.mem_A <= vm.mem + d) continue;
        temp.push_back(server);
    }
    if(temp.empty()){
        for(auto &server: serverManager.servers){
            if(server.cpu_A < vm.cpu || server.mem_A < vm.mem) continue;
            temp.push_back(server);
        }
    }
    sort(temp.begin(), temp.end(), server_cmp);
    return temp[0].type;
}

bool canAssign(Server &server, VM &vm, int node) {
    bool fa = server.cpu_A >= vm.cpu && server.mem_A >= vm.mem;
    bool fb = server.cpu_B >= vm.cpu && server.mem_B >= vm.mem;
    if(node == 0){  // 能否双节点部署
        return fa && fb;
    }else if(node == 1){  // 能否部署在A节点
        return fa;
    }else{  // 能否部署在B节点
        return fb;
    }
}

void doAssign(Server &server, VM &vm, int node) {
    server.vms_id.insert(vm.id);
    vm.serverID = server.id;
    vm.assign_node = node;
    if(node == 0){
        server.cpu_A -= vm.cpu, server.mem_A -= vm.mem;
        server.cpu_B -= vm.cpu, server.mem_B -= vm.mem;
        server.f ++ ;
    }else if(node == 1){
        server.cpu_A -= vm.cpu, server.mem_A -= vm.mem;
    }else{
        server.cpu_B -= vm.cpu, server.mem_B -= vm.mem;
    }
}

void undoAssign(Server &server, VM &vm, int node) {
    server.vms_id.erase(vm.id);
    vm.serverID = -1;
    vm.assign_node = -1;
    if(node == 0){
        server.cpu_A += vm.cpu, server.mem_A += vm.mem;
        server.cpu_B += vm.cpu, server.mem_B += vm.mem;
        server.f -- ;
    }else if(node == 1){
        server.cpu_A += vm.cpu, server.mem_A += vm.mem;
    }else{
        server.cpu_B += vm.cpu, server.mem_B += vm.mem;
    }
}

void delVm(VM &vm) {
    Server &server = serverManager.ID2Server[vm.serverID];
    server.vms_id.erase(vm.id);
    if(vm.isTwoNodes){
        server.cpu_A += vm.cpu, server.mem_A += vm.mem;
        server.cpu_B += vm.cpu, server.mem_B += vm.mem;
        server.f -- ;
    }else{
        if(vm.assign_node == 1){
            server.cpu_A += vm.cpu, server.mem_A += vm.mem;
        }else{
            server.cpu_B += vm.cpu, server.mem_B += vm.mem;
        }
    }
}

vector<Query> reorderQuery(vector<Query> &dayQuery) {
    vector<vector<Query>> list;
    vector<Query> temp;
    for(auto &q: dayQuery){
        if(!temp.empty() && q.type != temp.back().type){
            list.push_back(temp);
            temp.clear();
        }
        temp.push_back(q);
    }
    if(!temp.empty()) list.push_back(temp);
    // 对list中每个部分重排序
    for(auto &item: list){
        if(item.back().type == "del") continue;
        sort(item.begin(), item.end(), query_cmp);
    }
    temp.clear();
    for(auto &item: list){
        for(auto &q: item){
            temp.push_back(q);
        }
    }
    return temp;
}

vector<Query> readDayQuery(){
    vector<Query> dayQuery;  // 存放一天的请求
    int R; cin >> R;
    for(int j = 0; j < R; j ++ ) {
        Query q;
        string type;
        cin >> type;
        type = type.substr(1), type.pop_back();
        q.type = type;

        if (q.type == "add") {
            string vm_type;
            cin >> vm_type;
            vm_type.pop_back();
            q.vm_type = vm_type;
        }

        string id;
        cin >> id;
        id.pop_back();
        q.vm_id = stoi(id);
        if (q.type == "add") {

            trueid2id[q.vm_id] = VMID_CNT;
            id2trueid[VMID_CNT] = q.vm_id;

            VM &vm = vmManager.type2VM[q.vm_type];
            vm.id = VMID_CNT;
            q.vm_id = VMID_CNT;
            vm.assign_node = -1;
            vmManager.ID2VM.push_back(vm);

            VMID_CNT ++ ;
//            vmsList.push_back(vm.id);
        }else{
            q.vm_id = trueid2id[q.vm_id];
        }
        dayQuery.push_back(q);
    }
    return dayQuery;
}

void readData()
{
    // 读取服务器数据
    int N; cin >> N;
    for(int i = 0; i < N; i ++ ){
        Server server;
        string type; cin >> type;
        type = type.substr(1); type.pop_back();
        server.type = type;

        string cpu; cin >> cpu;
        cpu.pop_back();
        server.cpu = stoi(cpu);
        server.cpu_A = server.cpu / 2;
        server.cpu_B = server.cpu / 2;

        string mem; cin >> mem;
        mem.pop_back();
        server.mem = stoi(mem);
        server.mem_A = server.mem / 2;
        server.mem_B = server.mem / 2;

        string cost; cin >> cost;
        cost.pop_back();
        server.hardware_cost = stoi(cost);

        cin >> cost;
        cost.pop_back();
        server.day_cost = stoi(cost);
        server.vms_id.clear();
        serverManager.type2Server[server.type] = server;
        serverManager.servers.push_back(server);
    }

    // 读取虚拟机数据
    int M; cin >> M;
    for(int i = 0; i < M; i ++ ){
        VM vm;
        string type; cin >> type;
        type = type.substr(1), type.pop_back();
        vm.type = type;

        string cpu; cin >> cpu;
        cpu.pop_back();
        vm.cpu = stoi(cpu);

        string mem; cin >> mem;
        mem.pop_back();
        vm.mem = stoi(mem);

        string flag; cin >> flag;
        flag.pop_back();
        vm.isTwoNodes = stoi(flag);
        if(vm.isTwoNodes){
            vm.cpu /= 2;
            vm.mem /= 2;
        }
        vm.serverID = -2;
        vmManager.type2VM[vm.type] = vm;
    }
}

void processOutput(int last, vector<string> &mig, vector <Query> &dayQuery){
    map<string, vector<Server>> mp;  // 记录每种服务器及其数目
    for(int id = last + 1; id <= serverManager.serverID; id ++ ){
        Server &server = serverManager.ID2Server[id];
        mp[server.type].push_back(server);
    }
    serverManager.serverID = last;
    for(auto &it: mp){
        for(auto &server: it.second){
            serverManager.serverID ++ ;
            int id = serverManager.serverID;
            server.id = id;
            for(auto &vm_id: server.vms_id){
                VM &vm = vmManager.ID2VM[vm_id];
                vm.serverID = id;
            }
            serverManager.ID2Server[id] = server;
        }
    }
    printf("(purchase, %d)\n", mp.size());
    for(auto &it: mp){
        string s = "(" + it.first + ", " + to_string(it.second.size()) + ")";
        puts(s.c_str());
    }
    printf("(migration, %d)\n", mig.size());
    for(string &s: mig){
        puts(s.c_str());
    }
    for(auto &q: dayQuery){
        VM &vm = vmManager.ID2VM[q.vm_id];
        if(q.type == "add") {
            string s = to_string(vm.serverID);
            if(vm.assign_node == 1) s += ", A";
            if(vm.assign_node == 2) s += ", B";
            s = "(" + s + ")";
            puts(s.c_str());
        }
    }
    fflush(stdout);
}

bool ServerManager::isEmpty(Server &server) {
    if(server.cpu_A + server.cpu_B == server.cpu && server.mem_A + server.mem_B == server.mem){
        return true;
    }
    return false;
}

long long ServerManager::getEnergyCost() {
    long long cost = 0;
    for(auto &it: ID2Server){
        auto &server = it;
        if(!isEmpty(server)) cost += server.day_cost;
    }
    return cost;
}

long long ServerManager::getHardwareCost() {
    long long cost = 0;
    for(auto &it: ID2Server){
        auto &server = it;
        cost += server.hardware_cost;
    }
    return cost;
}

int VmManager::getMigrationNum() const {
    int cnt = 3 * num / 100;
    return cnt;
}
